package main.leetcode.offer.firstround.from51to68;

import java.util.Arrays;

/**
 * 59-I.滑动窗口的最大值
 *
 * <p>给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
 *
 * <p>提示：你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex59I {
    public static void main(String[] args) {
        System.out.println(
                Arrays.toString(
                        new ex59I().maxSlidingWindow(new int[] {1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }

    // 单调双向队列
    //    public int[] maxSlidingWindow(int[] nums, int k) {
    //        int n = nums.length;
    //        if (n < k) return nums;
    //        int[] res = new int[n - k + 1];
    //        // 维护单调队列
    //        LinkedList<Integer> list = new LinkedList<>();
    //        for (int i = 0; i < n; ++i) {
    //            while (!list.isEmpty() && nums[i] >= nums[list.peekLast()]) {
    //                list.pollLast();
    //            }
    //            list.addLast(i);
    //            // 当前窗口不包括当前最大值所在位置
    //            if (list.peekFirst() <= i - k) {
    //                list.pollFirst();
    //            }
    //            // 已经到达第一个窗口右界限
    //            if (i >= k - 1) {
    //                res[i - k + 1] = nums[list.peekFirst()];
    //            }
    //        }
    //        return res;
    //    }

    // 动态规划
    // 思路：将数组划分为块，每个块大小为k，除了最后一个可能会小于k个元素
    // 辅助数组：
    //      left[]存储每块从左到右的最大值，每块块尾即为当前块中最大值；
    //      right[]存储每块从右到左的最大值，每块块首即为当前块中最大值
    // 滑动窗口只有两种情况，① 正好和某块重合；②横跨两个窗口
    //  对①，left在该块中的最大值肯定和right在该块中的最大值相同，res取任意皆可
    //  对②，当前滑动窗口必定包含左边块块尾，和，右边块块首，即，必定包含了两块各自的最大值，因此取 max(left[], right[])即可
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n < k || k <= 1) return nums;
        int[] res = new int[n - k + 1];
        int[] left = new int[n];
        int[] right = new int[n];

        // 从左到右
        for (int i = 1; i < n; ++i) {
            if (i % k == 0) left[i] = nums[i]; // 块首
            else left[i] = Math.max(left[i - 1], nums[i]);
        }

        // 从右到左
        for (int i = n - 2; i >= 0; --i) {
            if ((i + 1) % k == 0) right[i] = nums[i]; // 块尾
            else right[i] = Math.max(right[i + 1], nums[i]);
        }

        // 滑动窗口
        for (int i = 0; i < n - k + 1; i++) {
            res[i] = Math.max(left[i + k - 1], right[i]);
        }

        return res;
    }
}
